# 数组中的逆序对： https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
class Solution:
    def reversePairs(self, nums: list) -> int:
        """
            利用归并排序计算：
            思想：先计算相邻的数之间的 逆序对个数， 在计算不相邻的， 也就是 两两比较再 合并后 4 4 比较。。计算逆序对后，便可以进行排序，因为不影响和其他不相邻元素的比较
        """
        t = [0] * len(nums)
        count = 0

        def Merge(nums, t, l, mid, r):
            nonlocal count
            for i in range(l, r + 1):
                t[i] = nums[i]
            
            # 用来统计count数量
            # for j in range(mid + 1, r + 1): 
            #     for i in range(l, mid + 1):
            #         if t[j] < t[i]: 
            #             count += mid - i + 1
            #             break
            
            i, k, j = l, l, mid + 1
            while i <= mid and j <= r:
                if t[i] > t[j]:
                    nums[k] = t[j]
                    # 当 t[i] > t[j], 那么因为有序， t[i] 到 t[mid] 都大于 t[j] , 逆序对数量为 mid - i + 1
                    count += mid - i + 1
                    j += 1
                else:
                    nums[k] = t[i]
                    i += 1
                k += 1
            
            while i <= mid: nums[k] = t[i]; i += 1; k += 1
            while j <= r: nums[k] = t[j]; j += 1; k += 1

        def MergeSort(nums, t, l, r):
            """ 归并排序步骤 """
            if l < r:
                mid = (l + r) // 2
                MergeSort(nums, t, l, mid)
                MergeSort(nums, t, mid + 1, r)
                Merge(nums, t, l, mid, r)
        
        MergeSort(nums, t, 0, len(nums)-1)
        print(nums)
        return count 



# 不使用 nonlocal 关键字， return 返回的写法
class Solution:
    def reversePairs(self, nums: list) -> int:
        """
            利用归并排序计算：
            思想：先计算相邻的数之间的 逆序对个数， 在计算不相邻的， 也就是 两两比较再 合并后 4 4 比较。。计算逆序对后，便可以进行排序，因为不影响和其他不相邻元素的比较
        """
        t = [0] * len(nums)

        def Merge(nums, t, l, mid, r):
            count = 0
            for i in range(l, r + 1):
                t[i] = nums[i]
            
            i, k, j = l, l, mid + 1
            while i <= mid and j <= r:
                if t[i] > t[j]:
                    nums[k] = t[j]
                    # 当 t[i] > t[j], 那么因为有序， t[i] 到 t[mid] 都大于 t[j] , 逆序对数量为 mid - i + 1
                    count += mid - i + 1
                    j += 1
                else:
                    nums[k] = t[i]
                    i += 1
                k += 1
            
            while i <= mid: nums[k] = t[i]; i += 1; k += 1
            while j <= r: nums[k] = t[j]; j += 1; k += 1

            return count 

        def MergeSort(nums, t, l, r):
            """ 归并排序步骤 """
            if l < r:
                mid = (l + r) // 2
                left_count = MergeSort(nums, t, l, mid)
                right_count = MergeSort(nums, t, mid + 1, r)
                merge_count = Merge(nums, t, l, mid, r)

                return left_count + right_count + merge_count
            else:
                return 0
        
        return MergeSort(nums, t, 0, len(nums)-1)
        

